// 给定一个经过编码的字符串，返回它解码后的字符串。

// 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

// 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

// 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

//  

// 示例 1：

// 输入：s = "3[a]2[bc]"
// 输出："aaabcbc"
// 示例 2：

// 输入：s = "3[a2[c]]"
// 输出："accaccacc"
// 示例 3：

// 输入：s = "2[abc]3[cd]ef"
// 输出："abcabccdcdcdef"
// 示例 4：

// 输入：s = "abc3[cd]xyz"
// 输出："abccdcdcdxyz"

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/* 栈
时间复杂度：O(n) // 解码后得出的字符串长度
空间复杂度：O(n)
*/
class Solution {
public:
    string decodeString(string s) {
        vector<string> stack{};
        int n = s.size();
        int i{0};
        while (i < n) {
            char c = s[i];
            if (isdigit(c)) {
                // 获取第一个数字并进栈
                string digits = getDigits(s, i);
                stack.push_back(digits);
            } else if (isalpha(c) || c == '[') {
                // 获取第一个字母并进栈
                stack.push_back(string(1, s[i++]));
            } else {
                ++i;
                vector<string> sub{};
                while (stack.back() != "[") {
                    sub.push_back(stack.back());
                    stack.pop_back();
                }
                reverse(sub.begin(), sub.end());
                stack.pop_back(); // 左括号出栈
                int count = stoi(stack.back()); // 重复的次数
                stack.pop_back();
                string t{};
                string o = getString(sub);
                while (count--) {
                    t += o;
                }
                stack.push_back(t);
            }
        }
        return getString(stack);
    }
    string getDigits(string& s, int& i) {
        string res{""};
        while (isdigit(s[i])) {
            res.push_back(s[i++]);
        }
        return res;
    }
    string getString(vector<string>& v) {
        string res{""};
        for (const auto& s : v) {
            res += s;
        }
        return res;
    }
};

/* 递归
时间复杂度：O(n) // 解码后得出的字符串长度
空间复杂度：O(n)
*/
class Solution {
public:
    string src; 
    size_t ptr;

    int getDigits() {
        int ret = 0;
        while (ptr < src.size() && isdigit(src[ptr])) {
            ret = ret * 10 + src[ptr++] - '0';
        }
        return ret;
    }

    string getString() {
        if (ptr == src.size() || src[ptr] == ']') {
            // String -> EPS
            return "";
        }

        char cur = src[ptr]; int repTime = 1;
        string ret;

        if (isdigit(cur)) {
            // String -> Digits [ String ] String
            // 解析 Digits
            repTime = getDigits(); 
            // 过滤左括号
            ++ptr;
            // 解析 String
            string str = getString(); 
            // 过滤右括号
            ++ptr;
            // 构造字符串
            while (repTime--) ret += str; 
        } else if (isalpha(cur)) {
            // String -> Char String
            // 解析 Char
            ret = string(1, src[ptr++]);
        }
        
        return ret + getString();
    }

    string decodeString(string s) {
        src = s;
        ptr = 0;
        return getString();
    }
};